|
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space ''n'' log ''n'' than in space ''n''. The somewhat weaker analogous theorems for time are the time hierarchy theorems. The foundation for the hierarchy theorems lies in the intuition that with either more time or more space comes the ability to compute more functions (or decide more languages). The hierarchy theorems are used to demonstrate that the time and space complexity classes form a hierarchy where classes with tighter bounds contain fewer languages than those with more relaxed bounds. Here we define and prove the space hierarchy theorem. The space hierarchy theorems rely on the concept of space-constructible functions. The deterministic and nondeterministic space hierarchy theorems state that for all space-constructible functions ''f''(''n''), :, where SPACE stands for either DSPACE or NSPACE, and refers to the little o notation. == Statement == Formally, a function is space-constructible if and there exists a Turing machine which computes the function in space when starting with an input , where represents a string of s. Most of the common functions that we work with are space-constructible, including polynomials, exponents, and logarithms. For every space-constructible function , there exists a language that is decidable in space but not in space . == Proof == The goal here is to define a language that can be decided in space but not space . Here we define the language : Now, for any machine that decides a language in space , will differ in at least one spot from the language of , namely at the value of . The algorithm for deciding the language is as follows: # On an input , compute using space-constructibility, and mark off cells of tape. Whenever an attempt is made to use more than cells, ''reject''. # If is not of the form for some TM , ''reject''. # Simulate on input for at most steps (using space). If the simulation tries to use more than space or more than operations, then ''reject''. # If accepted during this simulation, then ''reject''; otherwise, ''accept''. Note on step 3: Execution is limited to steps in order to avoid the case where does not halt on the input . That is, the case where consumes space of only as required, but runs for infinite time. The above proof holds for the case of PSPACE whereas we must make some change for the case of NPSPACE. The crucial point is that while on a deterministic TM we may easily invert acceptance and rejection (crucial for step 4), this is not possible on a non-deterministic machine. For the case of NPSPACE we will first modify step 4 to: # If accepted during this simulation, then ''accept''; otherwise, ''reject''. We will now prove by contradiction that can not be decided by a TM using cells. Assuming can be decided by a TM using cells, and following from the Immerman–Szelepcsényi theorem follows that can also be determined by a TM (which we will call ) using cells. Here lies the contradiction, therefore our assumption must be false: # If (for some large enough k) is not in then will accept it, therefore rejects , therefore is in (contradiction). # If (for some large enough k) is in then will reject it, therefore accepts , therefore is not in (contradiction). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Space hierarchy theorem」の詳細全文を読む スポンサード リンク
|